#include "headfiles.h"

using namespace std;

static bool isPossibleLocation(int *column_loc, int row_no, int j) {
    int i;
    for (i = 0; i < row_no; i++) {
        if (column_loc[i] == j ||
            (row_no - i) == (j - column_loc[i])) {
            return false;
        }
    }

    return true;
}

void printArrange(int *column_loc, int board_size) {
    int i, j;
    for (i = 0; i < board_size; i++) {
        for (j = 0; j < column_loc[i]; j++) {
            cout << "x\t";
        }
        cout << column_loc[i] << "\t";
        j++;
        for (; j < board_size; j++) {
            cout << "x\t";
        }
        cout << endl;
    }
    cout << endl;

    return;
}

void calcQueenLocationRecur(int *column_loc, int row_no, int board_size) {
    if (row_no >= board_size) {
        cout << "Queen are arranged, with locations being:" << endl;
        printArrange(column_loc, board_size);
//        int i;
//        for (i = 0; i < board_size; i++) {
//            cout << "(" << i << ", " << column_loc[i] << ")" << endl;
//        }
//        cout << endl;
    }
    else {
        int j;
        for (j = 0; j < board_size; j++) {
            bool flag;
            flag = isPossibleLocation(column_loc, row_no, j);
            if (flag) {
                column_loc[row_no] = j;
                calcQueenLocationRecur(column_loc, row_no + 1, board_size);
            }
        }
    }

    return;
}

void arrangeQueens(int board_size) {
    if (board_size <= 0) {
        cout << "Invalid board size: " << board_size << endl;
        return;
    }

    int *column_loc = (int *)malloc(sizeof(int) * board_size);
    if (column_loc == NULL) {
        cout << "Allocate column location array error!" << endl;
        return;
    }

    calcQueenLocationRecur(column_loc, 0, board_size);

    free(column_loc);

    return;
}

